package com.desheng.bigdata.ds.array;

import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;

/**
 * @Description 可变链表
 * @Author deshenglijun
 * @Date 2020/5/5 14:06
 * @Version 1.0
 */
public class MyArrayList<E> implements Iterable<E> {

    private E[] elements; //内部元素
    private int size;  //
    private final int DEFAULT_CAPACITY = 10;
    public MyArrayList(int capacity) {
        this.elements = (E[]) new Object[capacity];
    }
    public MyArrayList() {
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
    /**
     * 将指定的元素添加到此列表的尾部。
     * @param e
     * @return
     */
    public boolean add(E e) {
        if(this.size == elements.length) {
            E[] objs = (E[]) new Object[elements.length + elements.length / 2];
            System.arraycopy(elements, 0, objs, 0, elements.length);
            this.elements = objs;
        }
        elements[size++] = e;
        return true;
    }

    /**
     * 将指定的元素插入此列表中的指定位置。
     * @param index
     * @param element
     */
    public void add(int index, E element) {
        checkIndex(index);
        if(size == elements.length) {
            E[] objs = (E[]) new Object[elements.length + elements.length / 2];
            System.arraycopy(elements, 0, objs, 0, elements.length);
            this.elements = objs;
        }
        System.arraycopy(elements, index, elements, index + 1, size - index);
        elements[index] = element;
        size++;
    }
    private void checkIndex(int index) {
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    }
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }
    /**
     * 按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。
     * @param c
     * @return
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        if(size + numNew > elements.length) {
            E[] objs = (E[]) new Object[size + numNew + (size + numNew)/ 2];
            System.arraycopy(elements, 0, objs, 0, elements.length);
            elements = objs;
        }
        System.arraycopy(a, 0, elements, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    /**
     * 移除此列表中的所有元素。
     */
    public void clear() {
        this.size = 0;
    }

    /**
     * 如果此列表中包含指定的元素，则返回 true。
     * @param o
     * @return
     */
    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }


    /**
     * 返回此列表中指定位置上的元素。
     * @param index
     * @return
     */
    public E get(int index) {
        checkIndex(index);
        return elements[index];
    }

    /**
     *  返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。
     * @param o
     * @return
     */
    public int indexOf(Object o) {
        if(null == o) {
            for(int i = 0; i < size; i++) {
                if(elements[i] == null) {
                    return i;
                }
            }
        } else {
            for(int i = 0; i < size; i++) {
                if(elements[i].equals(o)) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 如果此列表中没有元素，则返回 true
     * @return
     */
    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。
     * @param o
     * @return
     */
    public int lastIndexOf(Object o) {
        if(null == o) {
            for(int i = size - 1; i >= 0; i--) {
                if(elements[i] == null) {
                    return i;
                }
            }
        } else {
            for(int i = size - 1; i >= 0; i--) {
                if(elements[i].equals(o)) {
                    return i;
                }
            }
        }
        return -1;
    }

    /**
     * 移除此列表中指定位置上的元素。
     * @param index
     * @return
     */
    public E remove(int index) {
        checkIndex(index);
        E oldValue = get(index);
        System.arraycopy(elements, index + 1, elements, index, size - index - 1);
        elements[--size] = null;
        return oldValue;
    }

    /**
     * 移除此列表中首次出现的指定元素（如果存在）。
     * @param o
     * @return
     */
    public boolean remove(Object o) {
        if(null == o) {
            for(int i = 0; i < size; i++) {
                if(elements[i] == null) {
                    remove(i);
                    return true;
                }
            }
        } else {
            for(int i = 0; i < size; i++) {
                if(elements[i].equals(o)) {
                    remove(i);
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 用指定的元素替代此列表中指定位置上的元素。
     * @param index
     * @param element
     * @return
     */
    public E set(int index, E element) {
        checkIndex(index);
        E oldValue = get(index);
        elements[index] = element;
        return oldValue;
    }

    /**
     * 返回此列表中的元素数。
     * @return
     */
    public int size() {
        return this.size;
    }

    /**
     *  按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。
     * @return
     */
    public Object[] toArray() {
        return Arrays.copyOf(elements, size);
    }

    /**
     * 按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。
     * @param a
     * @param <T>
     * @return
     */
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            return (T[]) Arrays.copyOf(elements, size, a.getClass());
        System.arraycopy(elements, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private int cursor;

            @Override
            public boolean hasNext() {
                return this.cursor < size;
            }

            @Override
            public E next() {
                return elements[cursor++];
            }
        };
    }
    //[1, 2, 3, 4, 5]
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            if(i != size -1) {
                sb.append(elements[i]).append(", ");
            } else {
                sb.append(elements[i]);
            }
        }

        sb.append("]");
        return sb.toString();
    }
}
